#lang sicp
(define (make-queue)
  (let ((front-pointer nil)
        (rear-pointer nil))
    (define (insert! v)
      (let ((item (list v)))
        (if (null? front-pointer)
            (begin
              (set! front-pointer item)
              (set! rear-pointer item))
            (begin
              (set-cdr! rear-pointer item)
              (set! rear-pointer item)))
        front-pointer))
    (define (delete!)
      (if (null? front-pointer)
          (error "queue is empty!")
          (begin
            (set! front-pointer (cdr front-pointer))))
      front-pointer)
    (define (empty?)
      (null? front-pointer))
    (define (front)
      (if (empty?)
          (error "EMPTY QUEUE -- make-queue!")
          (car front)))
    (define (dispatch msg)
      (cond ((eq? msg 'delete!) delete!)
            ((eq? msg 'insert!) insert!)
            ((eq? msg 'front) front)
            (else
             (error "UNKNOWN MESSAGE! -- make-queue" msg))))
    dispatch))

(define (delete-queue! queue)
  ((queue 'delete!)))
(define (insert-queue! queue v)
  ((queue 'insert!) v))



(define q1 (make-queue))
(insert-queue! q1 1)
(insert-queue! q1 'b)
(insert-queue! q1 'c)
(delete-queue! q1)
(delete-queue! q1)


;;3.23
(define (make-deque) (cons (list) (list)))
(define (front-ptr-deque deque)
  (car deque))
(define (rear-ptr-deque deque)
  (cdr deque))
(define (set-front-ptr-deque! deque item)
  (set-car! deque item))
(define (set-rear-ptr-deque! deque item)
  (set-cdr! deque item))

(define (make-item-deque pre v next)
  (list pre v next))
(define (pre-item-deque item)
  (car item))
(define (next-item-deque item)
  (caddr item))
(define (value-item-deque item)
  (cadr item))
(define (set-pre-item-deque! item ptr)
  (set-car! item ptr))
(define (set-next-item-deque! item ptr)
  (set-car! (cddr item) ptr))
(define (connect-item-deque! item1 item2)
  (set-pre-item-deque! item2 item1)
  (set-next-item-deque! item1 item2))
(define (pre-delete-item-deque! item)
  (set-pre-item-deque! item nil))
(define (next-delete-item-deque! item)
  (set-next-item-deque! item nil))

(define (empty-deque? deque)
  (null? (front-ptr-deque deque)))

(define (front-deque deque)
  (if (empty-deque? deque)
      (error "EMPTY DEQUEUE! -- FRONT-DEQUE")
      (value-item-deque (front-ptr-deque deque))))
(define (rear-deque deque)
  (if (empty-deque? deque)
      (error "EMPTY DEQUEUE! -- REAR-DEQUE")
      (value-item-deque (rear-ptr-deque deque))))

(define (front-insert-deque! deque v)
  (let ((item (make-item-deque nil v nil)))
    (cond ((empty-deque? deque)
           (set-front-ptr-deque! deque item)
           (set-rear-ptr-deque! deque item))
          (else
           (connect-item-deque! item (front-ptr-deque deque))
           (set-front-ptr-deque! deque item))))
  (print-deque deque))

(define (rear-insert-deque! deque v)
  (let ((item (make-item-deque nil v nil)))
    (cond ((empty-deque? deque)
           (set-front-ptr-deque! deque item)
           (set-rear-ptr-deque! deque item))
          (else
           (connect-item-deque! (rear-ptr-deque deque) item)
           (set-rear-ptr-deque! deque item))))
  (print-deque deque))

(define (front-delete-deque! deque)
  (cond ((empty-deque? deque)
         (error "EMPTY DEQUE! -- front-delete-deque!"))
        (else
         (let ((item (front-ptr-deque deque)))
           (set-front-ptr-deque! deque (next-item-deque item))
           (if (null? (front-ptr-deque deque))
               ""
               (pre-delete-item-deque! (next-item-deque item))))))
  (print-deque deque))

(define (rear-delete-deque! deque)
  (cond ((empty-deque? deque)
         (error "EMPTY DEQUE! -- rear-delete-deque!"))
        (else
         (let ((item (rear-ptr-deque deque)))
           (set-rear-ptr-deque! deque (pre-item-deque item))
           (if (null? (rear-ptr-deque deque))
               (set-front-ptr-deque! deque nil)
               (next-delete-item-deque! (pre-item-deque item))))))
  (print-deque deque))

(define (print-deque deque)
  (let ((head (front-ptr-deque deque)))
    (define (iter-print item)
      (if (null? item)
          ""
          (begin 
            (display (value-item-deque item))
            (display " ")
            (iter-print (next-item-deque item)))))
    (newline)
    (display "{ ")
    (iter-print head)
    (display "}")))


(display "deque test:")

(define dq1 (make-deque))
(front-insert-deque! dq1 'a)
(front-insert-deque! dq1 'b)
(rear-insert-deque! dq1 'c)
(rear-insert-deque! dq1 'd)

(rear-delete-deque! dq1)
(rear-delete-deque! dq1)
(rear-delete-deque! dq1)
(rear-delete-deque! dq1)

(rear-insert-deque! dq1 'c)
(rear-insert-deque! dq1 'd)
(front-insert-deque! dq1 'a)
(front-insert-deque! dq1 'b)

(front-delete-deque! dq1)
(front-delete-deque! dq1)
(front-delete-deque! dq1)
(front-delete-deque! dq1)
